import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class SudokuResolver {
	
	private final static int NB_LIGNE_COLONNE = 9;

	private int[][] grille = new int[NB_LIGNE_COLONNE][NB_LIGNE_COLONNE];
	private boolean[][] casesInvalide= new boolean[NB_LIGNE_COLONNE][NB_LIGNE_COLONNE];
	
	private boolean grilleComplete;
			
	public static void main(String[] args) {
		SudokuResolver sudRes = new SudokuResolver();
		sudRes.lireFichier(args[0]);
		
		long time = System.currentTimeMillis();
		
		sudRes.resoudreSudoku(0, 0);
		
		System.out.println("Temps d'exécution : " + (System.currentTimeMillis() - time) + " ms");
		
		sudRes.afficherGrille();
		
	}
	
	void afficherGrille()
	{
		for(int x = 0; x < NB_LIGNE_COLONNE; x++)
		{
			for(int y = 0; y < NB_LIGNE_COLONNE; y++)
			{
				System.out.print(grille[x][y]);
			}
			System.out.println();
		}
	}

	void lireFichier(final String nomFichier)
	{
		try {
			FileReader fr = new FileReader(nomFichier);
			
			for(int x = 0; x < NB_LIGNE_COLONNE; x++) {
				for(int y = 0; y < NB_LIGNE_COLONNE; y++) {
					String chiffre = String.valueOf((char)fr.read());
					grille[x][y] = Integer.parseInt(chiffre);
					
					if(grille[x][y] != 0) {
						casesInvalide[x][y] = true;
					}
				}
				fr.skip(2); //skip \n\r
			}
			
			fr.close();
			
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	boolean estValide(final int x, final int y, final int k)
	{
		for(int cpt = 0; cpt < NB_LIGNE_COLONNE; cpt++)
		{
			if(grille[x][cpt] == k || grille[cpt][y] == k)
				return false;	
		}
		
		final int limiteX = (x/3) * 3;
		final int limiteY = (y/3) * 3;
		
		for(int cpt = 0; cpt < 3; cpt++)
		{
			final int posX = limiteX + cpt;
			
			if(grille[posX][limiteY] == k)
				return false;
			
			if(grille[posX][limiteY + 1] == k)
				return false;
			
			if(grille[posX][limiteY + 2] == k)
				return false;
		}
		
		return true;
	}
	
	boolean grilleTerminer()
	{
		for(int x = 0; x < NB_LIGNE_COLONNE; x++)
		{
			for(int y = 0; y < NB_LIGNE_COLONNE; y++)
			{
				if (grille[x][y] == 0)
					return false;
			}
		}
		
		this.grilleComplete = true;
		return true;
	}
	
	void resoudreSudoku(final int x, final int y)
	{		
		if(grille[x][y] != 0)
		{
			if (x < (NB_LIGNE_COLONNE - 1)) {
				resoudreSudoku(x+1, y);
			}
			else if (y < (NB_LIGNE_COLONNE - 1)) {
				resoudreSudoku(0, y+1);
			}
			
			return;
		}
		
		for (int k = 1; k <= NB_LIGNE_COLONNE; k++) {
			if (estValide(x, y, k)) {
				
				int valeurOriginale = grille[x][y];
				grille[x][y] = k;
				
				if (x < (NB_LIGNE_COLONNE - 1)) {
					resoudreSudoku(x+1, y);
				}
				else if (y < (NB_LIGNE_COLONNE - 1)) {
					resoudreSudoku(0, y+1);
				}
				else {
					return;
				}
				
				if (grilleComplete || grilleTerminer()) {
					break;
				}
				else {
					grille[x][y] = valeurOriginale;
				}
			}
		}
		
		if (x == 0 && y == 0 && !grilleComplete) {
			// Sudoku impossible
		}
	}
}
